package LeetCode;

public class Code59_generateMatrix {

    // 1,2,3,4对应上下左右

    int[][] res;

    public int[][] generateMatrix(int n) {
        this.res = new int[n][n];
        dfs(0, 0, 1, 4);
        return res;
    }

    private void dfs(int i, int j, int number, int direction) {
        if (!isIllegal(i, j)){
            return;
        }
        if (res[i][j] != 0){
            return;
        }
        // 终止条件
        if (number > res.length * res.length){
            return;
        }
        res[i][j] = number;
        // 继续往这个方向走
        if (direction == 1){
            if (isIllegal(i-1, j) && res[i-1][j] == 0){
                dfs(i-1, j, number+1, 1);
            } else {
                // 向右
                dfs(i, j+1, number+1, 4);
            }
        } else if (direction == 2){
            if (isIllegal(i+1, j) && res[i+1][j] == 0){
                dfs(i+1, j, number+1, 2);
            } else{
                // 向左
                dfs(i, j-1, number+1, 3);
            }
        } else if (direction == 3){
            if (isIllegal(i, j-1) && res[i][j-1] == 0){
                dfs(i, j-1, number+1, 3);
            } else{
                // 向上
                dfs(i-1, j, number+1, 1);
            }
        } else if (direction == 4){
            if (isIllegal(i, j+1) && res[i][j+1] == 0){
                dfs(i, j+1, number+1, 4);
            } else{
                // 向下
                dfs(i+1, j, number+1, 2);
            }
        }
    }

    private boolean isIllegal(int i, int j) {
        if (i < 0 || i >= res.length ||
                j < 0 || j >= res[0].length){
            return false;
        }
        return true;
    }
}
